Analysis of the Parallel Distinguished Point Tradeoff
Identifieur interne : 000509 ( Main/Exploration ); précédent : 000508; suivant : 000510Analysis of the Parallel Distinguished Point Tradeoff
Auteurs : Jin Hong [Corée du Sud] ; Won Lee [Corée du Sud] ; Daegun Ma [Corée du Sud]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
Abstract
Abstract: Cryptanalytic time memory tradeoff algorithms are tools for quickly inverting one-way functions and many consider the rainbow table method to be the most efficient tradeoff algorithm. However, it was recently announced, mostly based on experiments, that the parallelization of the perfect distinguished point tradeoff algorithm brings about an algorithm that is 50% more efficient than the perfect rainbow table method. Motivated by this claim, we provide an accurate theoretic analysis of the parallel version of the non-perfect distinguished point tradeoff algorithm. Performance differences between different tradeoff algorithms are usually not very large, but even these small differences can be crucial in practice. So we take care not to ignore the side effects of false alarms while analyzing the online time complexity of the parallel distinguished point tradeoff algorithm. Our complexity results are used to compare the parallel non-perfect distinguished point tradeoff against the non-perfect rainbow table method. The two algorithms are compared under identical success rate requirements and the pre-computation efforts are taken into account. Contrary to our anticipation, we find that the rainbow table method is superior in typical situations, even though the parallelization did have a positive effect on the efficiency of the distinguished point tradeoff algorithm.
Url:
DOI: 10.1007/978-3-642-25578-6_14
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001848
- to stream Istex, to step Curation: 001750
- to stream Istex, to step Checkpoint: 000166
- to stream Main, to step Merge: 000515
- to stream Main, to step Curation: 000509
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Analysis of the Parallel Distinguished Point Tradeoff</title><author><name sortKey="Hong, Jin" sort="Hong, Jin" uniqKey="Hong J" first="Jin" last="Hong">Jin Hong</name></author><author><name sortKey="Lee, Won" sort="Lee, Won" uniqKey="Lee W" first="Won" last="Lee">Won Lee</name></author><author><name sortKey="Ma, Daegun" sort="Ma, Daegun" uniqKey="Ma D" first="Daegun" last="Ma">Daegun Ma</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:3AD54DE946A06B97B847C49D10D7DE900D6AC3D4</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-25578-6_14</idno><idno type="url">https://api.istex.fr/document/3AD54DE946A06B97B847C49D10D7DE900D6AC3D4/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001848</idno><idno type="wicri:Area/Istex/Curation">001750</idno><idno type="wicri:Area/Istex/Checkpoint">000166</idno><idno type="wicri:doubleKey">0302-9743:2011:Hong J:analysis:of:the</idno><idno type="wicri:Area/Main/Merge">000515</idno><idno type="wicri:Area/Main/Curation">000509</idno><idno type="wicri:Area/Main/Exploration">000509</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Analysis of the Parallel Distinguished Point Tradeoff</title><author><name sortKey="Hong, Jin" sort="Hong, Jin" uniqKey="Hong J" first="Jin" last="Hong">Jin Hong</name><affiliation wicri:level="4"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Department of Mathematical Sciences and ISaC, Seoul National University, 151-747, Seoul</wicri:regionArea><placeName><settlement type="city">Séoul</settlement></placeName><orgName type="university">Université nationale de Séoul</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Lee, Won" sort="Lee, Won" uniqKey="Lee W" first="Won" last="Lee">Won Lee</name><affiliation wicri:level="4"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Department of Mathematical Sciences and ISaC, Seoul National University, 151-747, Seoul</wicri:regionArea><placeName><settlement type="city">Séoul</settlement></placeName><orgName type="university">Université nationale de Séoul</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Ma, Daegun" sort="Ma, Daegun" uniqKey="Ma D" first="Daegun" last="Ma">Daegun Ma</name><affiliation wicri:level="3"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Department of Mathematics, Konkuk University, 143-701, Seoul</wicri:regionArea><placeName><settlement type="city">Séoul</settlement></placeName></affiliation><affiliation><wicri:noCountry code="no comma">E-mail: ma.daegun@gmail.com</wicri:noCountry></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2011</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">3AD54DE946A06B97B847C49D10D7DE900D6AC3D4</idno><idno type="DOI">10.1007/978-3-642-25578-6_14</idno><idno type="ChapterID">14</idno><idno type="ChapterID">Chap14</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Cryptanalytic time memory tradeoff algorithms are tools for quickly inverting one-way functions and many consider the rainbow table method to be the most efficient tradeoff algorithm. However, it was recently announced, mostly based on experiments, that the parallelization of the perfect distinguished point tradeoff algorithm brings about an algorithm that is 50% more efficient than the perfect rainbow table method. Motivated by this claim, we provide an accurate theoretic analysis of the parallel version of the non-perfect distinguished point tradeoff algorithm. Performance differences between different tradeoff algorithms are usually not very large, but even these small differences can be crucial in practice. So we take care not to ignore the side effects of false alarms while analyzing the online time complexity of the parallel distinguished point tradeoff algorithm. Our complexity results are used to compare the parallel non-perfect distinguished point tradeoff against the non-perfect rainbow table method. The two algorithms are compared under identical success rate requirements and the pre-computation efforts are taken into account. Contrary to our anticipation, we find that the rainbow table method is superior in typical situations, even though the parallelization did have a positive effect on the efficiency of the distinguished point tradeoff algorithm.</div></front></TEI><affiliations><list><country><li>Corée du Sud</li></country><settlement><li>Séoul</li></settlement><orgName><li>Université nationale de Séoul</li></orgName></list><tree><country name="Corée du Sud"><noRegion><name sortKey="Hong, Jin" sort="Hong, Jin" uniqKey="Hong J" first="Jin" last="Hong">Jin Hong</name></noRegion><name sortKey="Hong, Jin" sort="Hong, Jin" uniqKey="Hong J" first="Jin" last="Hong">Jin Hong</name><name sortKey="Lee, Won" sort="Lee, Won" uniqKey="Lee W" first="Won" last="Lee">Won Lee</name><name sortKey="Lee, Won" sort="Lee, Won" uniqKey="Lee W" first="Won" last="Lee">Won Lee</name><name sortKey="Ma, Daegun" sort="Ma, Daegun" uniqKey="Ma D" first="Daegun" last="Ma">Daegun Ma</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000509 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000509 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:3AD54DE946A06B97B847C49D10D7DE900D6AC3D4
|texte= Analysis of the Parallel Distinguished Point Tradeoff
}}
| This area was generated with Dilib version V0.6.32. |  |